<!DOCTYPE html>
<html lang="zh-cn" itemscope itemtype="http://schema.org/WebPage">
<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <title> - 友知弄</title>
  

<meta name="renderer" content="webkit" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>

<meta name="MobileOptimized" content="width"/>
<meta name="HandheldFriendly" content="true"/>


<meta name="applicable-device" content="pc,mobile">

<meta name="theme-color" content="#f8f5ec" />
<meta name="msapplication-navbutton-color" content="#f8f5ec">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="#f8f5ec">

<meta name="mobile-web-app-capable" content="yes">

<meta name="author" content="yixy" />
  <meta name="description" content="基础数据结构——二叉树-树-森林 1. 二叉树 二叉树( Binary Tree)是一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
 二叉树：树的度小于等于2的有序树。  二叉树具有下列重要特性：
 在二叉树的第i层上至多有2^(i-1)个结点（i≥1）利用归纳法容易证得此性质。 深度为k的二叉树至多有2^k-1个结点（k≥1） 对任意二叉树，若其叶子结点树为n0，度为2的结点数为n2，则n0=n2&#43;1。   等差数列前n项和：n(a1&#43;an)/2 等比数列前n项和：a1(1-q^n)/(1-q)
设二叉树中度为0的结点为n0，度为1的结点为n1，度为2的结点为n2。 分支数量B=n0&#43;n1&#43;n2-1=2*n2&#43;n1，按结点上连分支计算和结点下连分支计算。
 2. 满二叉树和完全二叉树  满二叉树：深度为k且有2^k-1个结点的二叉树。  可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，从左至右，由此可以引出完全二叉树的定义。注意，不同的资料对完全二叉树的定义可能不同。
 完全二叉树：深度为 k有 n个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度 k的满二叉树，序号为1到n的节点一对一对应时，称为完全二叉树。  完全二叉树的性质：
 具有n个结点的完全二叉树深度为|logn|&#43;1。（log底为2） 含n个结点的完全二叉树，其序号为i的结点：1）若i=1，则根是i；若i&amp;gt;1，则父亲结点是m[i/2]。（m[]向下取整，M[]向上取整）；2）若2i&amp;gt;n，则结点i无左孩子（i为叶子结点），否则其左孩子为2i；3）若2i&#43;1&amp;gt;n，则结点i无右孩子，否则其右孩子结点是2i&#43;1。  3. 二叉树的存储  顺序存储结构：结点按序号顺序存储，无结点需要特殊标识占位。适合完全二叉树，对于插入、删除结点效率很低。 二叉链表：data,leftchild指针,rightchild指针 三叉链表：data,leftchild指针,rightchild指针,parent指针  4. 遍历二叉树和线索二叉树 遍历二叉树问题是指按某个路径巡访二叉树中每个结点，并保证每个结点仅被访问一次。一般采用递归方式实现，按对每个子树的根结点遍历的先后顺序有以下几种方式。
 前（根）序遍历：时间复杂度O(n) 中（根）序遍历：时间复杂度O(n) 后（根）序遍历：时间复杂度O(n)  实际上，遍历二叉树的其实就是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列或后序序列。这是一个对非线性结构进行线性化的操作。这些线性序列中的每一个元素都有且仅有一个前驱结点和后继结点。
当我们希望得到二叉树中某一个结点的前驱或者后继结点时，顺序存储结构的二叉树是可以很好得到的，但是对于二叉链表则是无法直接得到的，只能通过遍历一次二叉树得到。每当涉及到求解前驱或者后继就需要将二叉链表遍历一次，非常不方便。
观察二叉树的结构，我们发现指针域并没有充分的利用，有很多“NULL”，也就是存在很多空指针。 对于一个有n个结点的二叉链表，每个节点都有指向左右孩子的两个指针域，一共有2n个指针域。而n个结点的二叉树又有n-1条分支线数(除了头结点，每一条分支都指向一个结点)，也就是存在2n-(n-1)=n&#43;1个空指针域。这些指针域只是白白的浪费空间。因此, 可以用空链域来存放结点的前驱和后继。线索二叉树就是利用n&#43;1个空链域来存放结点的前驱和后继结点的信息。
 指向前驱和后继的指针叫做线索 ，加上线索的二叉树就称之为线索二叉树。  在每一个结点都增设两个标志域LTag和RTag，它们只存放0或1的布尔型变量，占用的空间很小。LTag为0是指向该结点的左孩子，为1时指向该结点的前驱。RTag为0是指向该结点的右孩子，为1时指向该结点的后继。
在中序线索二叉树上遍历二叉树，不需要递归，而且虽然时间复杂度仍为O(n)，但常数因子要比递归遍历算法小。若程序中所用二叉链表需要经常遍历或查找结点在遍历序列中的前驱和后继，则应采用线索链表作存储结构。
5. 树的存储结构  双亲表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指示器指示其双亲结点在顺序表中的位置。注意，这种方式求结点的孩子时需要遍历整个结构。   孩子表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指向单链表的指针，该单链表中存储该结点的孩子结点。注意，这种方式求结点的父亲时需要遍历整个结构。   双亲孩子表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指示器指示其双亲结点在顺序表中的位置，同时附设一个指向单链表的指针，该单链表中存储该结点的孩子结点。   树的二叉链表表示法：链表中结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。这样可以以二叉链表作为媒介导出树与二叉树之间的对应关系。  6." />

  <meta name="keywords" content="essay, notes" />






<meta name="generator" content="Hugo 0.56.1" />


<link rel="canonical" href="https://yixy.github.io/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/05%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BA%8C%E5%8F%89%E6%A0%91-%E6%A0%91-%E6%A3%AE%E6%9E%97/" />



<link rel="icon" href="/youzhilane/favicon.ico" />











<link rel="stylesheet" href="/youzhilane/sass/jane.min.af20b78e95c84de86b00a0242a4a77bd2601700e1b250edf27537d957ac0041d.css" integrity="sha256-ryC3jpXITehrAKAkKkp3vSYBcA4bJQ7fJ1N9lXrABB0=" media="screen" crossorigin="anonymous">





<meta property="og:title" content="" />
<meta property="og:description" content="基础数据结构——二叉树-树-森林 1. 二叉树 二叉树( Binary Tree)是一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
 二叉树：树的度小于等于2的有序树。  二叉树具有下列重要特性：
 在二叉树的第i层上至多有2^(i-1)个结点（i≥1）利用归纳法容易证得此性质。 深度为k的二叉树至多有2^k-1个结点（k≥1） 对任意二叉树，若其叶子结点树为n0，度为2的结点数为n2，则n0=n2&#43;1。   等差数列前n项和：n(a1&#43;an)/2 等比数列前n项和：a1(1-q^n)/(1-q)
设二叉树中度为0的结点为n0，度为1的结点为n1，度为2的结点为n2。 分支数量B=n0&#43;n1&#43;n2-1=2*n2&#43;n1，按结点上连分支计算和结点下连分支计算。
 2. 满二叉树和完全二叉树  满二叉树：深度为k且有2^k-1个结点的二叉树。  可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，从左至右，由此可以引出完全二叉树的定义。注意，不同的资料对完全二叉树的定义可能不同。
 完全二叉树：深度为 k有 n个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度 k的满二叉树，序号为1到n的节点一对一对应时，称为完全二叉树。  完全二叉树的性质：
 具有n个结点的完全二叉树深度为|logn|&#43;1。（log底为2） 含n个结点的完全二叉树，其序号为i的结点：1）若i=1，则根是i；若i&gt;1，则父亲结点是m[i/2]。（m[]向下取整，M[]向上取整）；2）若2i&gt;n，则结点i无左孩子（i为叶子结点），否则其左孩子为2i；3）若2i&#43;1&gt;n，则结点i无右孩子，否则其右孩子结点是2i&#43;1。  3. 二叉树的存储  顺序存储结构：结点按序号顺序存储，无结点需要特殊标识占位。适合完全二叉树，对于插入、删除结点效率很低。 二叉链表：data,leftchild指针,rightchild指针 三叉链表：data,leftchild指针,rightchild指针,parent指针  4. 遍历二叉树和线索二叉树 遍历二叉树问题是指按某个路径巡访二叉树中每个结点，并保证每个结点仅被访问一次。一般采用递归方式实现，按对每个子树的根结点遍历的先后顺序有以下几种方式。
 前（根）序遍历：时间复杂度O(n) 中（根）序遍历：时间复杂度O(n) 后（根）序遍历：时间复杂度O(n)  实际上，遍历二叉树的其实就是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列或后序序列。这是一个对非线性结构进行线性化的操作。这些线性序列中的每一个元素都有且仅有一个前驱结点和后继结点。
当我们希望得到二叉树中某一个结点的前驱或者后继结点时，顺序存储结构的二叉树是可以很好得到的，但是对于二叉链表则是无法直接得到的，只能通过遍历一次二叉树得到。每当涉及到求解前驱或者后继就需要将二叉链表遍历一次，非常不方便。
观察二叉树的结构，我们发现指针域并没有充分的利用，有很多“NULL”，也就是存在很多空指针。 对于一个有n个结点的二叉链表，每个节点都有指向左右孩子的两个指针域，一共有2n个指针域。而n个结点的二叉树又有n-1条分支线数(除了头结点，每一条分支都指向一个结点)，也就是存在2n-(n-1)=n&#43;1个空指针域。这些指针域只是白白的浪费空间。因此, 可以用空链域来存放结点的前驱和后继。线索二叉树就是利用n&#43;1个空链域来存放结点的前驱和后继结点的信息。
 指向前驱和后继的指针叫做线索 ，加上线索的二叉树就称之为线索二叉树。  在每一个结点都增设两个标志域LTag和RTag，它们只存放0或1的布尔型变量，占用的空间很小。LTag为0是指向该结点的左孩子，为1时指向该结点的前驱。RTag为0是指向该结点的右孩子，为1时指向该结点的后继。
在中序线索二叉树上遍历二叉树，不需要递归，而且虽然时间复杂度仍为O(n)，但常数因子要比递归遍历算法小。若程序中所用二叉链表需要经常遍历或查找结点在遍历序列中的前驱和后继，则应采用线索链表作存储结构。
5. 树的存储结构  双亲表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指示器指示其双亲结点在顺序表中的位置。注意，这种方式求结点的孩子时需要遍历整个结构。   孩子表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指向单链表的指针，该单链表中存储该结点的孩子结点。注意，这种方式求结点的父亲时需要遍历整个结构。   双亲孩子表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指示器指示其双亲结点在顺序表中的位置，同时附设一个指向单链表的指针，该单链表中存储该结点的孩子结点。   树的二叉链表表示法：链表中结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。这样可以以二叉链表作为媒介导出树与二叉树之间的对应关系。  6." />
<meta property="og:type" content="article" />
<meta property="og:url" content="https://yixy.github.io/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/05%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%BA%8C%E5%8F%89%E6%A0%91-%E6%A0%91-%E6%A3%AE%E6%9E%97/" />

<meta itemprop="name" content="">
<meta itemprop="description" content="基础数据结构——二叉树-树-森林 1. 二叉树 二叉树( Binary Tree)是一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
 二叉树：树的度小于等于2的有序树。  二叉树具有下列重要特性：
 在二叉树的第i层上至多有2^(i-1)个结点（i≥1）利用归纳法容易证得此性质。 深度为k的二叉树至多有2^k-1个结点（k≥1） 对任意二叉树，若其叶子结点树为n0，度为2的结点数为n2，则n0=n2&#43;1。   等差数列前n项和：n(a1&#43;an)/2 等比数列前n项和：a1(1-q^n)/(1-q)
设二叉树中度为0的结点为n0，度为1的结点为n1，度为2的结点为n2。 分支数量B=n0&#43;n1&#43;n2-1=2*n2&#43;n1，按结点上连分支计算和结点下连分支计算。
 2. 满二叉树和完全二叉树  满二叉树：深度为k且有2^k-1个结点的二叉树。  可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，从左至右，由此可以引出完全二叉树的定义。注意，不同的资料对完全二叉树的定义可能不同。
 完全二叉树：深度为 k有 n个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度 k的满二叉树，序号为1到n的节点一对一对应时，称为完全二叉树。  完全二叉树的性质：
 具有n个结点的完全二叉树深度为|logn|&#43;1。（log底为2） 含n个结点的完全二叉树，其序号为i的结点：1）若i=1，则根是i；若i&gt;1，则父亲结点是m[i/2]。（m[]向下取整，M[]向上取整）；2）若2i&gt;n，则结点i无左孩子（i为叶子结点），否则其左孩子为2i；3）若2i&#43;1&gt;n，则结点i无右孩子，否则其右孩子结点是2i&#43;1。  3. 二叉树的存储  顺序存储结构：结点按序号顺序存储，无结点需要特殊标识占位。适合完全二叉树，对于插入、删除结点效率很低。 二叉链表：data,leftchild指针,rightchild指针 三叉链表：data,leftchild指针,rightchild指针,parent指针  4. 遍历二叉树和线索二叉树 遍历二叉树问题是指按某个路径巡访二叉树中每个结点，并保证每个结点仅被访问一次。一般采用递归方式实现，按对每个子树的根结点遍历的先后顺序有以下几种方式。
 前（根）序遍历：时间复杂度O(n) 中（根）序遍历：时间复杂度O(n) 后（根）序遍历：时间复杂度O(n)  实际上，遍历二叉树的其实就是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列或后序序列。这是一个对非线性结构进行线性化的操作。这些线性序列中的每一个元素都有且仅有一个前驱结点和后继结点。
当我们希望得到二叉树中某一个结点的前驱或者后继结点时，顺序存储结构的二叉树是可以很好得到的，但是对于二叉链表则是无法直接得到的，只能通过遍历一次二叉树得到。每当涉及到求解前驱或者后继就需要将二叉链表遍历一次，非常不方便。
观察二叉树的结构，我们发现指针域并没有充分的利用，有很多“NULL”，也就是存在很多空指针。 对于一个有n个结点的二叉链表，每个节点都有指向左右孩子的两个指针域，一共有2n个指针域。而n个结点的二叉树又有n-1条分支线数(除了头结点，每一条分支都指向一个结点)，也就是存在2n-(n-1)=n&#43;1个空指针域。这些指针域只是白白的浪费空间。因此, 可以用空链域来存放结点的前驱和后继。线索二叉树就是利用n&#43;1个空链域来存放结点的前驱和后继结点的信息。
 指向前驱和后继的指针叫做线索 ，加上线索的二叉树就称之为线索二叉树。  在每一个结点都增设两个标志域LTag和RTag，它们只存放0或1的布尔型变量，占用的空间很小。LTag为0是指向该结点的左孩子，为1时指向该结点的前驱。RTag为0是指向该结点的右孩子，为1时指向该结点的后继。
在中序线索二叉树上遍历二叉树，不需要递归，而且虽然时间复杂度仍为O(n)，但常数因子要比递归遍历算法小。若程序中所用二叉链表需要经常遍历或查找结点在遍历序列中的前驱和后继，则应采用线索链表作存储结构。
5. 树的存储结构  双亲表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指示器指示其双亲结点在顺序表中的位置。注意，这种方式求结点的孩子时需要遍历整个结构。   孩子表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指向单链表的指针，该单链表中存储该结点的孩子结点。注意，这种方式求结点的父亲时需要遍历整个结构。   双亲孩子表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指示器指示其双亲结点在顺序表中的位置，同时附设一个指向单链表的指针，该单链表中存储该结点的孩子结点。   树的二叉链表表示法：链表中结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。这样可以以二叉链表作为媒介导出树与二叉树之间的对应关系。  6.">



<meta itemprop="wordCount" content="59">



<meta itemprop="keywords" content="" />
<meta name="twitter:card" content="summary"/>
<meta name="twitter:title" content=""/>
<meta name="twitter:description" content="基础数据结构——二叉树-树-森林 1. 二叉树 二叉树( Binary Tree)是一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。
 二叉树：树的度小于等于2的有序树。  二叉树具有下列重要特性：
 在二叉树的第i层上至多有2^(i-1)个结点（i≥1）利用归纳法容易证得此性质。 深度为k的二叉树至多有2^k-1个结点（k≥1） 对任意二叉树，若其叶子结点树为n0，度为2的结点数为n2，则n0=n2&#43;1。   等差数列前n项和：n(a1&#43;an)/2 等比数列前n项和：a1(1-q^n)/(1-q)
设二叉树中度为0的结点为n0，度为1的结点为n1，度为2的结点为n2。 分支数量B=n0&#43;n1&#43;n2-1=2*n2&#43;n1，按结点上连分支计算和结点下连分支计算。
 2. 满二叉树和完全二叉树  满二叉树：深度为k且有2^k-1个结点的二叉树。  可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，从左至右，由此可以引出完全二叉树的定义。注意，不同的资料对完全二叉树的定义可能不同。
 完全二叉树：深度为 k有 n个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度 k的满二叉树，序号为1到n的节点一对一对应时，称为完全二叉树。  完全二叉树的性质：
 具有n个结点的完全二叉树深度为|logn|&#43;1。（log底为2） 含n个结点的完全二叉树，其序号为i的结点：1）若i=1，则根是i；若i&gt;1，则父亲结点是m[i/2]。（m[]向下取整，M[]向上取整）；2）若2i&gt;n，则结点i无左孩子（i为叶子结点），否则其左孩子为2i；3）若2i&#43;1&gt;n，则结点i无右孩子，否则其右孩子结点是2i&#43;1。  3. 二叉树的存储  顺序存储结构：结点按序号顺序存储，无结点需要特殊标识占位。适合完全二叉树，对于插入、删除结点效率很低。 二叉链表：data,leftchild指针,rightchild指针 三叉链表：data,leftchild指针,rightchild指针,parent指针  4. 遍历二叉树和线索二叉树 遍历二叉树问题是指按某个路径巡访二叉树中每个结点，并保证每个结点仅被访问一次。一般采用递归方式实现，按对每个子树的根结点遍历的先后顺序有以下几种方式。
 前（根）序遍历：时间复杂度O(n) 中（根）序遍历：时间复杂度O(n) 后（根）序遍历：时间复杂度O(n)  实际上，遍历二叉树的其实就是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列或后序序列。这是一个对非线性结构进行线性化的操作。这些线性序列中的每一个元素都有且仅有一个前驱结点和后继结点。
当我们希望得到二叉树中某一个结点的前驱或者后继结点时，顺序存储结构的二叉树是可以很好得到的，但是对于二叉链表则是无法直接得到的，只能通过遍历一次二叉树得到。每当涉及到求解前驱或者后继就需要将二叉链表遍历一次，非常不方便。
观察二叉树的结构，我们发现指针域并没有充分的利用，有很多“NULL”，也就是存在很多空指针。 对于一个有n个结点的二叉链表，每个节点都有指向左右孩子的两个指针域，一共有2n个指针域。而n个结点的二叉树又有n-1条分支线数(除了头结点，每一条分支都指向一个结点)，也就是存在2n-(n-1)=n&#43;1个空指针域。这些指针域只是白白的浪费空间。因此, 可以用空链域来存放结点的前驱和后继。线索二叉树就是利用n&#43;1个空链域来存放结点的前驱和后继结点的信息。
 指向前驱和后继的指针叫做线索 ，加上线索的二叉树就称之为线索二叉树。  在每一个结点都增设两个标志域LTag和RTag，它们只存放0或1的布尔型变量，占用的空间很小。LTag为0是指向该结点的左孩子，为1时指向该结点的前驱。RTag为0是指向该结点的右孩子，为1时指向该结点的后继。
在中序线索二叉树上遍历二叉树，不需要递归，而且虽然时间复杂度仍为O(n)，但常数因子要比递归遍历算法小。若程序中所用二叉链表需要经常遍历或查找结点在遍历序列中的前驱和后继，则应采用线索链表作存储结构。
5. 树的存储结构  双亲表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指示器指示其双亲结点在顺序表中的位置。注意，这种方式求结点的孩子时需要遍历整个结构。   孩子表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指向单链表的指针，该单链表中存储该结点的孩子结点。注意，这种方式求结点的父亲时需要遍历整个结构。   双亲孩子表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指示器指示其双亲结点在顺序表中的位置，同时附设一个指向单链表的指针，该单链表中存储该结点的孩子结点。   树的二叉链表表示法：链表中结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。这样可以以二叉链表作为媒介导出树与二叉树之间的对应关系。  6."/>

<!--[if lte IE 9]>
  <script src="https://cdnjs.cloudflare.com/ajax/libs/classlist/1.1.20170427/classList.min.js"></script>
<![endif]-->

<!--[if lt IE 9]>
  <script src="https://cdn.jsdelivr.net/npm/html5shiv@3.7.3/dist/html5shiv.min.js"></script>
  <script src="https://cdn.jsdelivr.net/npm/respond.js@1.4.2/dest/respond.min.js"></script>
<![endif]-->




</head>
<body>
  <div id="mobile-navbar" class="mobile-navbar">
  <div class="mobile-header-logo">
    <a href="/youzhilane/" class="logo">友知弄</a>
  </div>
  <div class="mobile-navbar-icon">
    <span></span>
    <span></span>
    <span></span>
  </div>
</div>
<nav id="mobile-menu" class="mobile-menu slideout-menu">
  <ul class="mobile-menu-list">
    <li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/">主页</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/categories/">分类</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/booklist/">书单</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/about/">关于友知弄</a>
          
        
      </li><li class="mobile-menu-item">
        
          
          
            <a class="menu-item-link" href="https://github.com/yixy" rel="noopener" target="_blank">
              GitHub
              
              <i class="iconfont">
                <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M623.36 272.96 473.216 423.04C467.2 429.056 467.072 438.656 472.896 444.416c0 0-6.72-6.656 1.6 1.6C496.064 467.648 528.64 500.224 528.64 500.224 534.464 506.048 544 505.856 550.016 499.904l150.08-150.144 67.328 66.432c9.024 8.96 27.456 4.544 30.4-8.96 19.968-92.608 46.656-227.52 46.656-227.52 6.848-34.496-16.192-56.704-49.92-49.92 0 0-134.656 26.816-227.328 46.784C560.32 178.048 556.352 182.272 554.752 187.136c-3.2 6.208-3.008 14.208 3.776 20.992L623.36 272.96z"></path>
  <path d="M841.152 457.152c-30.528 0-54.784 24.512-54.784 54.656l0 274.752L237.696 786.56 237.696 237.696l206.016 0c6.656 0 10.752 0 13.248 0C487.68 237.696 512 213.184 512 182.848 512 152.32 487.36 128 456.96 128L183.04 128C153.216 128 128 152.576 128 182.848c0 3.136 0.256 6.272 0.768 9.28C128.256 195.136 128 198.272 128 201.408l0 639.488c0 0.064 0 0.192 0 0.256 0 0.128 0 0.192 0 0.32 0 30.528 24.512 54.784 54.784 54.784l646.976 0c6.592 0 9.728 0 11.712 0 28.736 0 52.928-22.976 54.464-51.968C896 843.264 896 842.304 896 841.344l0-20.352L896 561.408 896 512.128C896 481.792 871.424 457.152 841.152 457.152z"></path>
</svg>

              </i>
            </a>
          
        
      </li><li class="mobile-menu-item">
        
          
          <div class="mobile-menu-parent">
            <span class="mobile-submenu-open"></span>
            <a href="https://yixy.github.io/youzhilane/post/">
              归档
            </a>
          </div>
          <ul class="mobile-submenu-list">
            
              <li>
                <a href="https://yixy.github.io/youzhilane/post/">日期</a>
              </li>
            
              <li>
                <a href="https://yixy.github.io/youzhilane/tags/">标签</a>
              </li>
            
          </ul>
        
      </li>
    

    
  </ul>
</nav>


  
    






  <link rel="stylesheet" href="/youzhilane/lib/photoswipe/photoswipe.min.css" />
  <link rel="stylesheet" href="/youzhilane/lib/photoswipe/default-skin/default-skin.min.css" />




<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

<div class="pswp__bg"></div>

<div class="pswp__scroll-wrap">
    
    <div class="pswp__container">
      <div class="pswp__item"></div>
      <div class="pswp__item"></div>
      <div class="pswp__item"></div>
    </div>
    
    <div class="pswp__ui pswp__ui--hidden">
    <div class="pswp__top-bar">
      
      <div class="pswp__counter"></div>
      <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>
      <button class="pswp__button pswp__button--share" title="Share"></button>
      <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>
      <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>
      
      
      <div class="pswp__preloader">
        <div class="pswp__preloader__icn">
          <div class="pswp__preloader__cut">
            <div class="pswp__preloader__donut"></div>
          </div>
        </div>
      </div>
    </div>
    <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
      <div class="pswp__share-tooltip"></div>
    </div>
    <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
    </button>
    <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
    </button>
    <div class="pswp__caption">
      <div class="pswp__caption__center"></div>
    </div>
    </div>
    </div>
</div>

  

  

  

  <header id="header" class="header container">
    <div class="logo-wrapper">
  <a href="/youzhilane/" class="logo">
    
      友知弄
    
  </a>
</div>

<nav class="site-navbar">
  <ul id="menu" class="menu">
    
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/">主页</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/categories/">分类</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/booklist/">书单</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://yixy.github.io/youzhilane/about/">关于友知弄</a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          
            <a class="menu-item-link" href="https://github.com/yixy" rel="noopener" target="_blank">
              GitHub
              
              <i class="iconfont">
                <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M623.36 272.96 473.216 423.04C467.2 429.056 467.072 438.656 472.896 444.416c0 0-6.72-6.656 1.6 1.6C496.064 467.648 528.64 500.224 528.64 500.224 534.464 506.048 544 505.856 550.016 499.904l150.08-150.144 67.328 66.432c9.024 8.96 27.456 4.544 30.4-8.96 19.968-92.608 46.656-227.52 46.656-227.52 6.848-34.496-16.192-56.704-49.92-49.92 0 0-134.656 26.816-227.328 46.784C560.32 178.048 556.352 182.272 554.752 187.136c-3.2 6.208-3.008 14.208 3.776 20.992L623.36 272.96z"></path>
  <path d="M841.152 457.152c-30.528 0-54.784 24.512-54.784 54.656l0 274.752L237.696 786.56 237.696 237.696l206.016 0c6.656 0 10.752 0 13.248 0C487.68 237.696 512 213.184 512 182.848 512 152.32 487.36 128 456.96 128L183.04 128C153.216 128 128 152.576 128 182.848c0 3.136 0.256 6.272 0.768 9.28C128.256 195.136 128 198.272 128 201.408l0 639.488c0 0.064 0 0.192 0 0.256 0 0.128 0 0.192 0 0.32 0 30.528 24.512 54.784 54.784 54.784l646.976 0c6.592 0 9.728 0 11.712 0 28.736 0 52.928-22.976 54.464-51.968C896 843.264 896 842.304 896 841.344l0-20.352L896 561.408 896 512.128C896 481.792 871.424 457.152 841.152 457.152z"></path>
</svg>

              </i>
            </a>
          

        

      </li>
    
        <li class="menu-item">
        
          
          <a class="menu-item-link menu-parent" href="https://yixy.github.io/youzhilane/post/">归档</a>
          <ul class="submenu">
            
              <li>
                <a href="https://yixy.github.io/youzhilane/post/">日期</a>
              </li>
            
              <li>
                <a href="https://yixy.github.io/youzhilane/tags/">标签</a>
              </li>
            
          </ul>

        

      </li>
    

    
    

    
  </ul>
</nav>

  </header>

  <div id="mobile-panel">
    <main id="main" class="main bg-llight">
      <div class="content-wrapper">
        <div id="content" class="content container">
          <article class="post bg-white">
    
    <header class="post-header">
      <h1 class="post-title"></h1>
      
      <div class="post-meta">
        <time datetime="0001-01-01" class="post-time">
          0001-01-01
        </time>
        
        <span class="more-meta"> 约 59 字 </span>
          <span class="more-meta"> 预计阅读 1 分钟 </span>

        
        

        
        
      </div>
    </header>

    
    
<div class="post-toc" id="post-toc">
  <h2 class="post-toc-title">文章目录</h2>
  <div class="post-toc-content">
    <nav id="TableOfContents">
<ul>
<li><a href="#基础数据结构-二叉树-树-森林">基础数据结构——二叉树-树-森林</a>
<ul>
<li><a href="#1-二叉树">1. 二叉树</a></li>
<li><a href="#2-满二叉树和完全二叉树">2. 满二叉树和完全二叉树</a></li>
<li><a href="#3-二叉树的存储">3. 二叉树的存储</a></li>
<li><a href="#4-遍历二叉树和线索二叉树">4. 遍历二叉树和线索二叉树</a></li>
<li><a href="#5-树的存储结构">5. 树的存储结构</a></li>
<li><a href="#6-森林的存储结构">6. 森林的存储结构</a></li>
<li><a href="#7-树和森林的遍历">7. 树和森林的遍历</a></li>
</ul></li>
</ul>
</nav>
  </div>
</div>

    
    <div class="post-content">
      

<h1 id="基础数据结构-二叉树-树-森林">基础数据结构——二叉树-树-森林</h1>

<h2 id="1-二叉树">1. 二叉树</h2>

<p>二叉树( Binary Tree)是一种树型结构，它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。</p>

<ul>
<li>二叉树：树的度小于等于2的有序树。</li>
</ul>

<p>二叉树具有下列重要特性：</p>

<ul>
<li>在二叉树的第i层上至多有2^(i-1)个结点（i≥1）利用归纳法容易证得此性质。</li>
<li>深度为k的二叉树至多有2^k-1个结点（k≥1）</li>
<li>对任意二叉树，若其叶子结点树为n0，度为2的结点数为n2，则n0=n2+1。</li>
</ul>

<blockquote>
<p>等差数列前n项和：n(a1+an)/2
等比数列前n项和：a1(1-q^n)/(1-q)</p>

<p>设二叉树中度为0的结点为n0，度为1的结点为n1，度为2的结点为n2。
分支数量B=n0+n1+n2-1=2*n2+n1，按结点上连分支计算和结点下连分支计算。</p>
</blockquote>

<h2 id="2-满二叉树和完全二叉树">2. 满二叉树和完全二叉树</h2>

<ul>
<li>满二叉树：深度为k且有2^k-1个结点的二叉树。</li>
</ul>

<p>可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，从左至右，由此可以引出完全二叉树的定义。注意，不同的资料对完全二叉树的定义可能不同。</p>

<ul>
<li>完全二叉树：深度为 k有 n个节点的二叉树，当且仅当其中的每一节点，都可以和同样深度 k的满二叉树，序号为1到n的节点一对一对应时，称为完全二叉树。</li>
</ul>

<p>完全二叉树的性质：</p>

<ul>
<li>具有n个结点的完全二叉树深度为|logn|+1。（log底为2）</li>
<li>含n个结点的完全二叉树，其序号为i的结点：1）若i=1，则根是i；若i&gt;1，则父亲结点是<code>m[i/2]</code>。（<code>m[]</code>向下取整，<code>M[]</code>向上取整）；2）若2i&gt;n，则结点i无左孩子（i为叶子结点），否则其左孩子为2i；3）若2i+1&gt;n，则结点i无右孩子，否则其右孩子结点是2i+1。</li>
</ul>

<h2 id="3-二叉树的存储">3. 二叉树的存储</h2>

<ul>
<li>顺序存储结构：结点按序号顺序存储，无结点需要特殊标识占位。适合完全二叉树，对于插入、删除结点效率很低。</li>
<li>二叉链表：data,leftchild指针,rightchild指针</li>
<li>三叉链表：data,leftchild指针,rightchild指针,parent指针</li>
</ul>

<h2 id="4-遍历二叉树和线索二叉树">4. 遍历二叉树和线索二叉树</h2>

<p>遍历二叉树问题是指按某个路径巡访二叉树中每个结点，并保证每个结点仅被访问一次。一般采用递归方式实现，按对每个子树的根结点遍历的先后顺序有以下几种方式。</p>

<ul>
<li>前（根）序遍历：时间复杂度O(n)</li>
<li>中（根）序遍历：时间复杂度O(n)</li>
<li>后（根）序遍历：时间复杂度O(n)</li>
</ul>

<p>实际上，遍历二叉树的其实就是以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树中结点的先序序列、中序序列或后序序列。这是一个对非线性结构进行线性化的操作。这些线性序列中的每一个元素都有且仅有一个前驱结点和后继结点。</p>

<p>当我们希望得到二叉树中某一个结点的前驱或者后继结点时，顺序存储结构的二叉树是可以很好得到的，但是对于二叉链表则是无法直接得到的，只能通过遍历一次二叉树得到。每当涉及到求解前驱或者后继就需要将二叉链表遍历一次，非常不方便。</p>

<p>观察二叉树的结构，我们发现指针域并没有充分的利用，有很多“NULL”，也就是存在很多空指针。
对于一个有n个结点的二叉链表，每个节点都有指向左右孩子的两个指针域，一共有2n个指针域。而n个结点的二叉树又有n-1条分支线数(除了头结点，每一条分支都指向一个结点)，也就是存在2n-(n-1)=n+1个空指针域。这些指针域只是白白的浪费空间。因此, 可以用空链域来存放结点的前驱和后继。线索二叉树就是利用n+1个空链域来存放结点的前驱和后继结点的信息。</p>

<ul>
<li>指向前驱和后继的指针叫做线索 ，加上线索的二叉树就称之为线索二叉树。</li>
</ul>

<p>在每一个结点都增设两个标志域LTag和RTag，它们只存放0或1的布尔型变量，占用的空间很小。LTag为0是指向该结点的左孩子，为1时指向该结点的前驱。RTag为0是指向该结点的右孩子，为1时指向该结点的后继。</p>

<p>在中序线索二叉树上遍历二叉树，不需要递归，而且虽然时间复杂度仍为O(n)，但常数因子要比递归遍历算法小。若程序中所用二叉链表需要经常遍历或查找结点在遍历序列中的前驱和后继，则应采用线索链表作存储结构。</p>

<h2 id="5-树的存储结构">5. 树的存储结构</h2>

<ul>
<li>双亲表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指示器指示其双亲结点在顺序表中的位置。注意，这种方式求结点的孩子时需要遍历整个结构。</li>
</ul>

<p><img src="http://sweeat.me/树的双亲表示法.png" alt="树的双亲表示法.png" /></p>

<ul>
<li>孩子表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指向单链表的指针，该单链表中存储该结点的孩子结点。注意，这种方式求结点的父亲时需要遍历整个结构。</li>
</ul>

<p><img src="http://sweeat.me/树的孩子表示法.png" alt="树的孩子表示法.png" /></p>

<ul>
<li>双亲孩子表示法：以一组连续空间（顺序表）存储树的结点，每个结点中附设一个指示器指示其双亲结点在顺序表中的位置，同时附设一个指向单链表的指针，该单链表中存储该结点的孩子结点。</li>
</ul>

<p><img src="http://sweeat.me/树的双亲孩子表示法.png" alt="树的双亲孩子表示法.png" /></p>

<ul>
<li>树的二叉链表表示法：链表中结点的两个指针分别指向该结点的第一个孩子结点和下一个兄弟结点。这样可以以二叉链表作为媒介导出树与二叉树之间的对应关系。</li>
</ul>

<p><img src="http://sweeat.me/树的二叉链表表示法.png" alt="树的二叉链表表示法.png" /></p>

<h2 id="6-森林的存储结构">6. 森林的存储结构</h2>

<p>从树的二叉链表表示定义可知，任何一棵和树对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。</p>

<h2 id="7-树和森林的遍历">7. 树和森林的遍历</h2>

<p>前序、中序、后序遍历。</p>

<p>当以二叉链表作为存储结构时，可以借用二叉树的先序遍历和中序遍历算法实现。</p>

    </div>

    
    
<div class="post-copyright">
  <p class="copyright-item">
    <span class="item-title">文章作者</span>
    <span class="item-content">yixy</span>
  </p>
  <p class="copyright-item">
    <span class="item-title">上次更新</span>
    <span class="item-content">
      0001-01-01
      
    </span>
  </p>
  
  <p class="copyright-item">
    <span class="item-title">许可协议</span>
    <span class="item-content"><a rel="license noopener" href="https://creativecommons.org/licenses/by-nc-nd/4.0/" target="_blank">CC BY-NC-ND 4.0</a></span>
  </p>
</div>


    
    
<div class="post-reward">
  <input type="checkbox" name="reward" id="reward" hidden />
  <label class="reward-button" for="reward">赞赏支持</label>
  <div class="qr-code">
    
    
      <label class="qr-code-image" for="reward">
        <img class="image" src="/youzhilane/img/about/wechat.jpg">
        <span>微信打赏</span>
      </label>
    
  </div>
</div>

    <footer class="post-footer">
      

      
      <nav class="post-nav">
        
          <a class="prev" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/04%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E6%A0%91%E5%92%8C%E6%A3%AE%E6%9E%97%E7%9A%84%E5%AE%9A%E4%B9%89/">
            
            <i class="iconfont">
              <svg  class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M691.908486 949.511495l75.369571-89.491197c10.963703-12.998035 10.285251-32.864502-1.499144-44.378743L479.499795 515.267417 757.434875 204.940602c11.338233-12.190647 11.035334-32.285311-0.638543-44.850487l-80.46666-86.564541c-11.680017-12.583596-30.356378-12.893658-41.662889-0.716314L257.233596 494.235404c-11.332093 12.183484-11.041474 32.266891 0.657986 44.844348l80.46666 86.564541c1.772366 1.910513 3.706415 3.533476 5.750981 4.877077l306.620399 321.703933C662.505829 963.726242 680.945807 962.528973 691.908486 949.511495z"></path>
</svg>

            </i>
            <span class="prev-text nav-default"></span>
            <span class="prev-text nav-mobile">上一篇</span>
          </a>
        
          <a class="next" href="/youzhilane/post/01%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%A7%91%E5%AD%A6/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/06%E5%9F%BA%E7%A1%80%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84huffman%E6%A0%91/">
            <span class="next-text nav-default"></span>
            <span class="prev-text nav-mobile">下一篇</span>
            
            <i class="iconfont">
              <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="18" height="18">
  <path d="M332.091514 74.487481l-75.369571 89.491197c-10.963703 12.998035-10.285251 32.864502 1.499144 44.378743l286.278095 300.375162L266.565125 819.058374c-11.338233 12.190647-11.035334 32.285311 0.638543 44.850487l80.46666 86.564541c11.680017 12.583596 30.356378 12.893658 41.662889 0.716314l377.434212-421.426145c11.332093-12.183484 11.041474-32.266891-0.657986-44.844348l-80.46666-86.564541c-1.772366-1.910513-3.706415-3.533476-5.750981-4.877077L373.270379 71.774697C361.493148 60.273758 343.054193 61.470003 332.091514 74.487481z"></path>
</svg>

            </i>
          </a>
      </nav>
    </footer>
  </article>

  
  
  
  

  
  

  

  
  

  

  

  

    

  

        </div>
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="icon-links">
  
  
    <a href="mailto:youzhilane01@gmail.com" rel="me noopener" class="iconfont"
      title="email" >
      <svg class="icon" viewBox="0 0 1451 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="36" height="36">
  <path d="M664.781909 681.472759 0 97.881301C0 3.997201 71.046997 0 71.046997 0L474.477909 0 961.649408 0 1361.641813 0C1361.641813 0 1432.688811 3.997201 1432.688811 97.881301L771.345323 681.472759C771.345323 681.472759 764.482731 685.154773 753.594283 688.65053L753.594283 688.664858C741.602731 693.493018 729.424896 695.068979 718.077952 694.839748 706.731093 695.068979 694.553173 693.493018 682.561621 688.664858L682.561621 688.65053C671.644501 685.140446 664.781909 681.472759 664.781909 681.472759L664.781909 681.472759ZM718.063616 811.603883C693.779541 811.016482 658.879232 802.205449 619.10784 767.734955 542.989056 701.759633 0 212.052267 0 212.052267L0 942.809523C0 942.809523 0 1024 83.726336 1024L682.532949 1024 753.579947 1024 1348.948139 1024C1432.688811 1024 1432.688811 942.809523 1432.688811 942.809523L1432.688811 212.052267C1432.688811 212.052267 893.138176 701.759633 817.019477 767.734955 777.248 802.205449 742.347691 811.03081 718.063616 811.603883L718.063616 811.603883Z"></path>
</svg>

    </a>


<a href="https://yixy.github.io/youzhilane/index.xml" rel="noopener alternate" type="application/rss&#43;xml"
    class="iconfont" title="rss" target="_blank">
    <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="30" height="30">
  <path d="M819.157333 1024C819.157333 574.592 449.408 204.8 0 204.8V0c561.706667 0 1024 462.293333 1024 1024h-204.842667zM140.416 743.04a140.8 140.8 0 0 1 140.501333 140.586667A140.928 140.928 0 0 1 140.074667 1024C62.72 1024 0 961.109333 0 883.626667s62.933333-140.544 140.416-140.586667zM678.784 1024h-199.04c0-263.210667-216.533333-479.786667-479.744-479.786667V345.173333c372.352 0 678.784 306.517333 678.784 678.826667z"></path>
</svg>

  </a>
   
</div>

<div class="copyright">
  <span class="power-by">
    Powered by <a class="hexo-link" href="https://gohugo.io">Hugo</a>
  </span>
  <span class="division">|</span>
  <span class="theme-info">
    Theme - <a class="theme-link" href="https://github.com/xianmin/hugo-theme-jane">Jane</a>
  </span>

  <span class="copyright-year">
    &copy;
    2019
    <span class="heart">
      
      <i class="iconfont">
        <svg class="icon" viewBox="0 0 1025 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="14" height="14">
  <path d="M1000.1 247.9c-15.5-37.3-37.6-70.6-65.7-98.9-54.4-54.8-125.8-85-201-85-85.7 0-166 39-221.4 107.4C456.6 103 376.3 64 290.6 64c-75.1 0-146.5 30.4-201.1 85.6-28.2 28.5-50.4 61.9-65.8 99.3-16 38.8-24 79.9-23.6 122.2 0.7 91.7 40.1 177.2 108.1 234.8 3.1 2.6 6 5.1 8.9 7.8 14.9 13.4 58 52.8 112.6 102.7 93.5 85.5 209.9 191.9 257.5 234.2 7 6.1 15.8 9.5 24.9 9.5 9.2 0 18.1-3.4 24.9-9.5 34.5-30.7 105.8-95.9 181.4-165 74.2-67.8 150.9-138 195.8-178.2 69.5-57.9 109.6-144.4 109.9-237.3 0.1-42.5-8-83.6-24-122.2z"
   fill="#8a8a8a"></path>
</svg>

      </i>
    </span><span class="author">
        yixy
        
      </span></span>

  
  

  
</div>

    </footer>

    <div class="back-to-top" id="back-to-top">
      <i class="iconfont">
        
        <svg class="icon" viewBox="0 0 1024 1024" version="1.1"
  xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"
  width="35" height="35">
  <path d="M510.866688 227.694839 95.449397 629.218702l235.761562 0-2.057869 328.796468 362.40389 0L691.55698 628.188232l241.942331-3.089361L510.866688 227.694839zM63.840492 63.962777l894.052392 0 0 131.813095L63.840492 195.775872 63.840492 63.962777 63.840492 63.962777zM63.840492 63.962777"></path>
</svg>

      </i>
    </div>
  </div>
  
<script type="text/javascript" src="/youzhilane/lib/jquery/jquery-3.2.1.min.js"></script>
  <script type="text/javascript" src="/youzhilane/lib/slideout/slideout-1.0.1.min.js"></script>




<script type="text/javascript" src="/youzhilane/js/main.638251f4230630f0335d8c6748e53a96f94b72670920b60c09a56fdc8bece214.js" integrity="sha256-Y4JR9CMGMPAzXYxnSOU6lvlLcmcJILYMCaVv3Ivs4hQ=" crossorigin="anonymous"></script>












  
    <script type="text/javascript" src="/youzhilane/js/load-photoswipe.js"></script>
    <script type="text/javascript" src="/youzhilane/lib/photoswipe/photoswipe.min.js"></script>
    <script type="text/javascript" src="/youzhilane/lib/photoswipe/photoswipe-ui-default.min.js"></script>
  















</body>
</html>
